/* 
 * File:   main.cpp
 * Author: trunghpb
 *
 * Created on March 21, 2010, 10:38 AM

 ĐỀ SỐ 18

Cho mạng gồm N máy tính. Biết giữa hai máy tính đều được nối với nhau bằng hệ thống cable trực tiếp hoặc gián tiếp
thông qua một số máy tính trung gian. Để tiết kiệm cable nối, người ta nghĩ cách loại bỏ đi một số đường cable sao
cho ta vẫn nhận được một mạng máy tính liên thông. Hãy viết chương trình bỏ các đường cable cho mạng máy tính sao
cho hai điều kiện sau được thỏa mãn:
(iii)	Số các đường cable loại bỏ nhiều nhất có thể được;
(iv)	Số các đường cable đi vào hoặc đi ra máy tính thứ K (1<=K<=N) là nhiều nhất.

Dữ liệu vào cho bởi file mang.in theo khuôn dạng sau:

•	Dòng đầu tiên ghi lại hai số tự nhiên N và K. Hai số được viết cách nhau bởi một vài khoảng trống.
•	N dòng kế tiếp ghi lại ma trận vuông Aij (i, j = 1, 2, ..., N) là biểu diễn các tuyến cable nối. Trong đó, Aij = 1 biểu thị từ máy tính thứ i và máy tính thứ j có đường cable nối trực tiếp; Aij = 0 biểu thị từ máy tính thứ i và máy tính thứ j không có đường cable nối trực tiếp;
	Mạng máy tính liên thông với tối thiểu các đường cable nối tìm được ghi lại trong file ketqua.out theo khuôn dạng sau:
•	Dòng đầu tiên ghi lại số N là số máy tính của mạng và M và số các đường cable còn lại nối các máy tính;
•	M dòng kế tiếp ghi lại mỗi đường cable nối trực tiếp từ máy tính i đến máy tính j. Giá trị i và j được viết cách nhau một vài khoảng trống.

		Ví dụ với mạng máy tính được cho trong file mang.in sẽ cho ta file ketqua.out tương ứng.


 */

#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <math.h>
#include <string.h>

#define MAX 100
#define TRUE 1
#define FALSE 0

int M, N, K;
int a[MAX][MAX];
int chuaxet[MAX], dd[MAX], dc[MAX];

void init(){
    M = 0;
    for(int i = 0; i<N; i++) chuaxet[i] = TRUE;
    
}

void input(){
    FILE *fi;
    fi = fopen("mang.in", "r");
    fscanf(fi, "%d %d \n", &N, &K);

    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            fscanf(fi, "%d", &a[i][j]);
        }
    }
    fclose(fi);
}

void bfs(int u){
    int queue[MAX];
    int dau, cuoi, t;
    dau = cuoi = 0;
    queue[cuoi++] = u;
    chuaxet[u] = FALSE;
    do{
        t = queue[dau++];
        for(int v=0; v<N; v++){
            if(chuaxet[v] && a[t][v]){
                dd[M] = t;dc[M] = v;
                M++;
                chuaxet[v] = FALSE;
                queue[cuoi++] = v;
            }
        }
    }while(dau < cuoi);

}
void output(){
    FILE *fo;
    fo = fopen("ketqua.out", "w");
    fprintf(fo, "%d %d\n", N, M);
    for(int i=0; i<M; i++){
        fprintf(fo, "%d %d\n", dd[i] + 1, dc[i] + 1);
    }
    fclose(fo);
}

/*
 * 
 */
int main(int argc, char** argv) {
    input();
    init();
    bfs(K - 1);
    output();
    return (EXIT_SUCCESS);
}

